package com.edu.leetcode.dataStruct;

import java.util.TreeSet;

/**
 * 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个下标 i 和 j，
 * 使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 * 如果存在则返回 true，不存在返回 false。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/contains-duplicate-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @作者 five-five
 * @创建时间 2021/4/17
 */
public class Demo21 {
    public static void main(String[] args) {
        Demo21 demo21 = new Demo21();
        int[] nums = new int[]{-2147483648, 2147483647};
        boolean b = demo21.containsNearbyAlmostDuplicate(nums, 2, 3);
        System.out.println(b);
    }

    /**
     * @param nums 整数数组
     * @param k    abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k
     * @param t    abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k
     * @return true or false
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //数组不合法
        if (nums == null || nums.length == 0) {
            return false;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int abs1 = Math.abs(nums[i] - nums[j]);
                int abs2 = Math.abs(i - j);
                boolean flag1 = abs1 <= t && t >= 0 && t <= Math.pow(2, 31) - 1;
                boolean flag2 = abs2 <= k && k <= Math.pow(10, 4);
                if (flag1 && flag2) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicateByLeetcode(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }

}
